package leetcode_top;
import java.util.*;
import org.junit.*;

public class Ex341 {

     public interface NestedInteger {
        
             // @return true if this NestedInteger holds a single integer, rather than a nested list.
             public boolean isInteger();
        
             // @return the single integer that this NestedInteger holds, if it holds a single integer
             // Return null if this NestedInteger holds a nested list
             public Integer getInteger();
        
             // @return the nested list that this NestedInteger holds, if it holds a nested list
             // Return empty list if this NestedInteger holds a single integer
             public List<NestedInteger> getList();
         }
    public class NestedIterator implements Iterator<Integer> {

        Stack<Node> stack = new Stack<>();
        int idx;
    
        List<NestedInteger> curList;
        public NestedIterator(List<NestedInteger> nestedList) {
            idx = 0;
            curList = nestedList;
        }
     //[[1,1],2,[1,1]]
        @Override
        public Integer next() {
            if (idx == curList.size()) {
                Node node = stack.pop();
                curList = node.list;
                idx = node.idx;
            }
            NestedInteger cur = curList.get(idx++);
            if (cur.isInteger()) {
                return cur.getInteger();
            } else {
                stack.push(new Node(curList, idx));
                curList = cur.getList();
                idx = 0;
                return next();
            }
        }
    
        @Override
        public boolean hasNext() {
            return idx == curList.size() && !stack.isEmpty();
        }
    
        class Node {
            List<NestedInteger> list;
            int idx;
            public Node(List<NestedInteger> list, int idx) {
                this.list = list;
                this.idx = idx;
            }
        }
    }
    @Test
    public void test() {
        // Arrays.asList(new NestedInteger)        
    }

    class Solution {}
     class NestedIterator2 implements Iterator<Integer> {
        private Deque<NestedInteger> deque;
        public NestedIterator2(List<NestedInteger> nestedList) {
            deque = new ArrayDeque<>();
            for(int i = nestedList.size() - 1 ; i >= 0 ; i--){
                deque.addLast(nestedList.get(i));
            }
        }
    
        @Override
        public Integer next() {
            NestedInteger cur = deque.removeLast();
            return cur.getInteger();
        }
    
        @Override
        public boolean hasNext() {
            while(!deque.isEmpty()){
                NestedInteger top = deque.peekLast();
                if(top.isInteger()){
                    return true;
                }
                deque.removeLast();
                for(int i = top.getList().size() - 1 ; i >= 0 ; i--){
                    deque.addLast(top.getList().get(i));
                }
            }
            return false;
        }
    }
    
}
